/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
// n^2混一个
var nextGreaterElement1 = function (nums1, nums2) {
  const ans = []
  for (let i = 0; i < nums1.length; i++) {
    let flag = false
    let index = -1
    for (let j = 0; j < nums2.length; j++) {
      if (index > -1) {
        if (nums2[j] > nums1[i]) {
          ans.push(nums2[j])
          flag = true
          break
        }
      }
      if (nums2[j] == nums1[i]) {
        index = j
      }
    }
    if (!flag) ans.push(-1)
  }
  return ans
}
// 单调栈
// 求第一个大 用递减栈
// 求第一个小 用递增栈
var nextGreaterElement2 = function (nums1, nums2) {
  const stack = []
  let ans = [], map = new Map()
  for (let i = 0; i < nums2.length; i++) {
    while (stack.length !== 0 && stack[stack.length - 1] < nums2[i]) {
      let n = stack.pop()
      map.set(n, nums2[i])
    }
    stack.push(nums2[i])
  }
  for (let i = 0; i < nums1.length; i++) {
    if (map.has(nums1[i])) ans.push(map.get(nums1[i]))
    else ans.push(-1)
  }
  return ans
}
console.log(nextGreaterElement2([4, 1, 2], [1, 3, 4, 2]))